'''
冒泡排序：
第一个元素和右边所有元素对比，找到最大/小的元素，交换位置，直到所有完成。
'''

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # 标志位，用于检测是否发生了交换
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                # 交换元素
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # 如果没有发生交换，说明列表已经有序，提前退出
        if not swapped:
            break
    return arr
def test_bubble_sort():
    # 测试示例 1
    arr = [64, 34, 25, 12, 22, 11, 90]
    assert bubble_sort(arr) == [11, 12, 22, 25, 34, 64, 90], "测试示例 1 失败"
    
    # 测试示例 2: 已经有序的列表
    arr = [1, 2, 3, 4, 5]
    assert bubble_sort(arr) == [1, 2, 3, 4, 5], "测试示例 2 失败"
    
    # 测试示例 3: 逆序列表
    arr = [5, 4, 3, 2, 1]
    assert bubble_sort(arr) == [1, 2, 3, 4, 5], "测试示例 3 失败"
    
    # 测试示例 4: 包含重复元素的列表
    arr = [4, 2, 2, 8, 3, 3, 1]
    assert bubble_sort(arr) == [1, 2, 2, 3, 3, 4, 8], "测试示例 4 失败"
    
    # 测试示例 5: 空列表
    arr = []
    assert bubble_sort(arr) == [], "测试示例 5 失败"
    
    # 测试示例 6: 只有一个元素的列表
    arr = [1]
    assert bubble_sort(arr) == [1], "测试示例 6 失败"
    
    print("所有测试用例通过！")

# 运行测试
test_bubble_sort()